'''
@Author: shj
@Date: 2020-05-31 13:18:57
@LastEditTime: 2020-05-31 13:27:46
@LastEditors: shj
@Description:  斐波那契数列
@FilePath: /python3/algorithms/offer_code/7_fib.py
'''
'''
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

n<=39
'''
'''
思路：
fib从第三项开始，后一项的值是前两项之和
'''


class Solution:
    def Fibonacci(self, n):
        # write code here
        if n == 0 or n == 1:  # 排除特例
            return n

        (a, b) = (0, 1)
        # 计算
        for _ in range(n):
            (a, b) = (b, a + b)
        return a
